DP N
隣接するものをくっつける
くっつける順番によってコストが異なる
コストを最小化する問題
領域を定義域とするDP
領域が指定された時のその領域をくっつける最安コストを値としてDP
code:python
def solve(N, XS):
accum = list(accumulate(XS)) + 0 @lru_cache(maxsize=None)
def sub(L, R):
if L == R:
return 0
ret = INF
for x in range(L, R):
v = sub(L, x) + sub(x + 1, R)
if v < ret:
ret = v
return ret + accumR - accumL - 1 return sub(0, N - 1)
Cython
code:python
cdef sub(long L, long R):
cdef long long ret
if L == R:
return 0
if ret != 0:
return ret
ret = INF
for x in range(L, R):
v = sub(L, x) + sub(x + 1, R)
if v < ret:
ret = v
return ret
cdef solve(N, XS):
cdef long i
cdef long long v
v = 0
for i in range(N):
return sub(0, N - 1)